(function e(t, n, r) { function s(o, u) { if (!n[o]) { if (!t[o]) { var a = typeof require == "function" && require; if (!u && a) return a(o, !0); if (i) return i(o, !0); throw new Error("Cannot find module '" + o + "'") } var f = n[o] = { exports: {} }; t[o][0].call(f.exports, function (e) { var n = t[o][1][e]; return s(n ? n : e) }, f, f.exports, e, t, n, r) } return n[o].exports } var i = typeof require == "function" && require; for (var o = 0; o < r.length; o++) s(r[o]); return s })({ 1: [function (require, module, exports) { module.exports = require("topojson"); //topojson = }, { "topojson": 2}], 2: [ function (require, module, exports) { var topojson = module.exports = require("./topojson"); topojson.topology = require("./lib/topojson/topology"); topojson.simplify = require("./lib/topojson/simplify"); topojson.clockwise = require("./lib/topojson/clockwise"); topojson.filter = require("./lib/topojson/filter"); topojson.prune = require("./lib/topojson/prune"); topojson.bind = require("./lib/topojson/bind"); }, { "./lib/topojson/bind": 3, "./lib/topojson/clockwise": 6, "./lib/topojson/filter": 10, "./lib/topojson/prune": 13, "./lib/topojson/simplify": 15, "./lib/topojson/topology": 18, "./topojson": 29 }], 3: [function (require, module, exports) { var type = require("./type"), topojson = require("../../"); module.exports = function (topology, propertiesById) { var bind = type({ geometry: function (geometry) { var properties0 = geometry.properties, properties1 = propertiesById[geometry.id]; if (properties1) { if (properties0) for (var k in properties1) properties0[k] = properties1[k]; else for (var k in properties1) { geometry.properties = properties1; break; } } this.defaults.geometry.call(this, geometry); }, LineString: noop, MultiLineString: noop, Point: noop, MultiPoint: noop, Polygon: noop, MultiPolygon: noop }); for (var key in topology.objects) { bind.object(topology.objects[key]); } }; function noop() { } }, { "../../": 2, "./type": 28}], 4: [function (require, module, exports) { // Computes the bounding box of the specified hash of GeoJSON objects. module.exports = function (objects) { var x0 = Infinity, y0 = Infinity, x1 = -Infinity, y1 = -Infinity; function boundGeometry(geometry) { if (geometry && boundGeometryType.hasOwnProperty(geometry.type)) boundGeometryType[geometry.type](geometry); } var boundGeometryType = { GeometryCollection: function (o) { o.geometries.forEach(boundGeometry); }, Point: function (o) { boundPoint(o.coordinates); }, MultiPoint: function (o) { o.coordinates.forEach(boundPoint); }, LineString: function (o) { boundLine(o.coordinates); }, MultiLineString: function (o) { o.coordinates.forEach(boundLine); }, Polygon: function (o) { o.coordinates.forEach(boundLine); }, MultiPolygon: function (o) { o.coordinates.forEach(boundMultiLine); } }; function boundPoint(coordinates) { var x = coordinates[0], y = coordinates[1]; if (x < x0) x0 = x; if (x > x1) x1 = x; if (y < y0) y0 = y; if (y > y1) y1 = y; } function boundLine(coordinates) { coordinates.forEach(boundPoint); } function boundMultiLine(coordinates) { coordinates.forEach(boundLine); } for (var key in objects) { boundGeometry(objects[key]); } return [x0, y0, x1, y1]; }; }, {}], 5: [function (require, module, exports) { exports.name = "cartesian"; exports.formatDistance = formatDistance; exports.ringArea = ringArea; exports.absoluteArea = Math.abs; exports.triangleArea = triangleArea; exports.distance = distance; function formatDistance(d) { return d.toString(); } function ringArea(ring) { var i = 0, n = ring.length, area = ring[n - 1][1] * ring[0][0] - ring[n - 1][0] * ring[0][1]; while (++i < n) { area += ring[i - 1][1] * ring[i][0] - ring[i - 1][0] * ring[i][1]; } return -area * .5; // ensure clockwise pixel areas are positive } function triangleArea(triangle) { return Math.abs( (triangle[0][0] - triangle[2][0]) * (triangle[1][1] - triangle[0][1]) - (triangle[0][0] - triangle[1][0]) * (triangle[2][1] - triangle[0][1]) ); } function distance(x0, y0, x1, y1) { var dx = x0 - x1, dy = y0 - y1; return Math.sqrt(dx * dx + dy * dy); } }, {}], 6: [function (require, module, exports) { var type = require("./type"), systems = require("./coordinate-systems"), topojson = require("../../"); module.exports = function (object, options) { if (object.type === "Topology") clockwiseTopology(object, options); else clockwiseGeometry(object, options); }; function clockwiseGeometry(object, options) { var system = null; if (options) "coordinate-system" in options && (system = systems[options["coordinate-system"]]); var clockwisePolygon = clockwisePolygonSystem(system.ringArea, reverse); type({ LineString: noop, MultiLineString: noop, Point: noop, MultiPoint: noop, Polygon: function (polygon) { clockwisePolygon(polygon.coordinates); }, MultiPolygon: function (multiPolygon) { multiPolygon.coordinates.forEach(clockwisePolygon); } }).object(object); function reverse(array) { array.reverse(); } } function clockwiseTopology(topology, options) { var system = null; if (options) "coordinate-system" in options && (system = systems[options["coordinate-system"]]); var clockwisePolygon = clockwisePolygonSystem(ringArea, reverse); var clockwise = type({ LineString: noop, MultiLineString: noop, Point: noop, MultiPoint: noop, Polygon: function (polygon) { clockwisePolygon(polygon.arcs); }, MultiPolygon: function (multiPolygon) { multiPolygon.arcs.forEach(clockwisePolygon); } }); for (var key in topology.objects) { clockwise.object(topology.objects[key]); } function ringArea(ring) { return system.ringArea(topojson.feature(topology, { type: "Polygon", arcs: [ring] }).geometry.coordinates[0]); } // TODO It might be slightly more compact to reverse the arc. function reverse(ring) { var i = -1, n = ring.length; ring.reverse(); while (++i < n) ring[i] = ~ring[i]; } }; function clockwisePolygonSystem(ringArea, reverse) { return function (rings) { if (!(n = rings.length)) return; var n, areas = new Array(n), max = -Infinity, best, area, t; // Find the largest absolute ring area; this should be the exterior ring. for (var i = 0; i < n; ++i) { var area = Math.abs(areas[i] = ringArea(rings[i])); if (area > max) max = area, best = i; } // Ensure the largest ring appears first. if (best) { t = rings[best], rings[best] = rings[0], rings[0] = t; t = areas[best], areas[best] = areas[0], areas[0] = t; } if (areas[0] < 0) reverse(rings[0]); for (var i = 1; i < n; ++i) { if (areas[i] > 0) reverse(rings[i]); } }; } function noop() { } }, { "../../": 2, "./coordinate-systems": 8, "./type": 28}], 7: [function (require, module, exports) { // Given a hash of GeoJSON objects and an id function, invokes the id function // to compute a new id for each object that is a feature. The function is passed // the feature and is expected to return the new feature id, or null if the // feature should not have an id. module.exports = function (objects, id) { if (arguments.length < 2) id = function (d) { return d.id; }; function idObject(object) { if (object && idObjectType.hasOwnProperty(object.type)) idObjectType[object.type](object); } function idFeature(feature) { var i = id(feature); if (i == null) delete feature.id; else feature.id = i; } var idObjectType = { Feature: idFeature, FeatureCollection: function (collection) { collection.features.forEach(idFeature); } }; for (var key in objects) { idObject(objects[key]); } return objects; }; }, {}], 8: [function (require, module, exports) { module.exports = { cartesian: require("./cartesian"), spherical: require("./spherical") }; }, { "./cartesian": 5, "./spherical": 16}], 9: [function (require, module, exports) { // Given a TopoJSON topology in absolute (quantized) coordinates, // converts to fixed-point delta encoding. // This is a destructive operation that modifies the given topology! module.exports = function (topology) { var arcs = topology.arcs, i = -1, n = arcs.length; while (++i < n) { var arc = arcs[i], j = 0, m = arc.length, point = arc[0], x0 = point[0], y0 = point[1], x1, y1; while (++j < m) { point = arc[j]; x1 = point[0]; y1 = point[1]; arc[j] = [x1 - x0, y1 - y0]; x0 = x1; y0 = y1; } } return topology; }; }, {}], 10: [function (require, module, exports) { var type = require("./type"), prune = require("./prune"), clockwise = require("./clockwise"), systems = require("./coordinate-systems"), topojson = require("../../"); module.exports = function (topology, options) { var system = null, forceClockwise = true, // force exterior rings to be clockwise? minimumArea; if (options) "coordinate-system" in options && (system = systems[options["coordinate-system"]]), "minimum-area" in options && (minimumArea = +options["minimum-area"]), "force-clockwise" in options && (forceClockwise = !!options["force-clockwise"]); if (forceClockwise) clockwise(topology, options); // deprecated; for backwards-compatibility if (!(minimumArea > 0)) minimumArea = Number.MIN_VALUE; var filter = type({ LineString: noop, // TODO remove empty lines MultiLineString: noop, Point: noop, MultiPoint: noop, Polygon: function (polygon) { polygon.arcs = polygon.arcs.filter(ringArea); if (!polygon.arcs.length) { polygon.type = null; delete polygon.arcs; } }, MultiPolygon: function (multiPolygon) { multiPolygon.arcs = multiPolygon.arcs.map(function (polygon) { return polygon.filter(ringArea); }).filter(function (polygon) { return polygon.length; }); if (!multiPolygon.arcs.length) { multiPolygon.type = null; delete multiPolygon.arcs; } }, GeometryCollection: function (collection) { this.defaults.GeometryCollection.call(this, collection); collection.geometries = collection.geometries.filter(function (geometry) { return geometry.type != null; }); if (!collection.geometries.length) { collection.type = null; delete collection.geometries; } } }); for (var key in topology.objects) { filter.object(topology.objects[key]); } prune(topology, options); function ringArea(ring) { var topopolygon = { type: "Polygon", arcs: [ring] }, geopolygon = topojson.feature(topology, topopolygon), exterior = geopolygon.geometry.coordinates[0], exteriorArea = system.absoluteArea(system.ringArea(exterior)); return exteriorArea >= minimumArea; } }; function noop() { } }, { "../../": 2, "./clockwise": 6, "./coordinate-systems": 8, "./prune": 13, "./type": 28}], 11: [function (require, module, exports) { // Given a hash of GeoJSON objects, replaces Features with geometry objects. // This is a destructive operation that modifies the input objects! module.exports = function (objects) { function geomifyObject(object) { return (object && geomifyObjectType.hasOwnProperty(object.type) ? geomifyObjectType[object.type] : geomifyGeometry)(object); } function geomifyFeature(feature) { var geometry = feature.geometry; if (geometry == null) { feature.type = null; } else { geomifyGeometry(geometry); feature.type = geometry.type; if (geometry.geometries) feature.geometries = geometry.geometries; else if (geometry.coordinates) feature.coordinates = geometry.coordinates; } delete feature.geometry; return feature; } function geomifyGeometry(geometry) { if (!geometry) return { type: null }; if (geomifyGeometryType.hasOwnProperty(geometry.type)) geomifyGeometryType[geometry.type](geometry); return geometry; } var geomifyObjectType = { Feature: geomifyFeature, FeatureCollection: function (collection) { collection.type = "GeometryCollection"; collection.geometries = collection.features; collection.features.forEach(geomifyFeature); delete collection.features; return collection; } }; var geomifyGeometryType = { GeometryCollection: function (o) { var geometries = o.geometries, i = -1, n = geometries.length; while (++i < n) geometries[i] = geomifyGeometry(geometries[i]); }, MultiPoint: function (o) { if (!o.coordinates.length) { o.type = null; delete o.coordinates; } else if (o.coordinates.length < 2) { o.type = "Point"; o.coordinates = o.coordinates[0]; } }, LineString: function (o) { if (!o.coordinates.length) { o.type = null; delete o.coordinates; } }, MultiLineString: function (o) { for (var lines = o.coordinates, i = 0, N = 0, n = lines.length; i < n; ++i) { var line = lines[i]; if (line.length) lines[N++] = line; } if (!N) { o.type = null; delete o.coordinates; } else if (N < 2) { o.type = "LineString"; o.coordinates = lines[0]; } else { o.coordinates.length = N; } }, Polygon: function (o) { for (var rings = o.coordinates, i = 0, N = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; if (ring.length) rings[N++] = ring; } if (!N) { o.type = null; delete o.coordinates; } else { o.coordinates.length = N; } }, MultiPolygon: function (o) { for (var polygons = o.coordinates, j = 0, M = 0, m = polygons.length; j < m; ++j) { for (var rings = polygons[j], i = 0, N = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; if (ring.length) rings[N++] = ring; } if (N) { rings.length = N; polygons[M++] = rings; } } if (!M) { o.type = null; delete o.coordinates; } else if (M < 2) { o.type = "Polygon"; o.coordinates = polygons[0]; } else { polygons.length = M; } } }; for (var key in objects) { objects[key] = geomifyObject(objects[key]); } return objects; }; }, {}], 12: [function (require, module, exports) { module.exports = function (objects, filter) { function prefilterGeometry(geometry) { if (!geometry) return { type: null }; if (prefilterGeometryType.hasOwnProperty(geometry.type)) prefilterGeometryType[geometry.type](geometry); return geometry; } var prefilterGeometryType = { GeometryCollection: function (o) { var geometries = o.geometries, i = -1, n = geometries.length; while (++i < n) geometries[i] = prefilterGeometry(geometries[i]); }, Polygon: function (o) { for (var rings = o.coordinates, i = 0, N = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; if (filter(ring)) rings[N++] = ring; } if (!N) { o.type = null; delete o.coordinates; } else { o.coordinates.length = N; } }, MultiPolygon: function (o) { for (var polygons = o.coordinates, j = 0, M = 0, m = polygons.length; j < m; ++j) { for (var rings = polygons[j], i = 0, N = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; if (filter(ring)) rings[N++] = ring; } if (N) { rings.length = N; polygons[M++] = rings; } } if (!M) { o.type = null; delete o.coordinates; } else if (M < 2) { o.type = "Polygon"; o.coordinates = polygons[0]; } else { polygons.length = M; } } }; for (var key in objects) { objects[key] = prefilterGeometry(objects[key]); } return objects; }; }, {}], 13: [function (require, module, exports) { module.exports = function (topology, options) { var verbose = false, objects = topology.objects, oldArcs = topology.arcs, oldArcCount = oldArcs.length, newArcs = topology.arcs = [], newArcCount = 0, newIndexByOldIndex = new Array(oldArcs.length); if (options) "verbose" in options && (verbose = !!options["verbose"]); function pruneGeometry(geometry) { if (geometry && pruneGeometryType.hasOwnProperty(geometry.type)) pruneGeometryType[geometry.type](geometry); } var pruneGeometryType = { GeometryCollection: function (o) { o.geometries.forEach(pruneGeometry); }, LineString: function (o) { pruneArcs(o.arcs); }, MultiLineString: function (o) { o.arcs.forEach(pruneArcs); }, Polygon: function (o) { o.arcs.forEach(pruneArcs); }, MultiPolygon: function (o) { o.arcs.forEach(pruneMultiArcs); } }; function pruneArcs(arcs) { for (var i = 0, m = 0, n = arcs.length; i < n; ++i) { var oldIndex = arcs[i], oldReverse = oldIndex < 0 && (oldIndex = ~oldIndex, true), oldArc = oldArcs[oldIndex], newIndex; // Skip collapsed arc segments. if (oldArc.length < 3 && !oldArc[1][0] && !oldArc[1][1]) continue; // If this is the first instance of this arc, // record it under its new index. if ((newIndex = newIndexByOldIndex[oldIndex]) == null) { newIndexByOldIndex[oldIndex] = newIndex = newArcCount++; newArcs[newIndex] = oldArcs[oldIndex]; } arcs[m++] = oldReverse ? ~newIndex : newIndex; } // If all were collapsed, restore the last arc to avoid collapsing the line. if (!(arcs.length = m) && n) { // If this is the first instance of this arc, // record it under its new index. if ((newIndex = newIndexByOldIndex[oldIndex]) == null) { newIndexByOldIndex[oldIndex] = newIndex = newArcCount++; newArcs[newIndex] = oldArcs[oldIndex]; } arcs[0] = oldReverse ? ~newIndex : newIndex; } } function pruneMultiArcs(arcs) { arcs.forEach(pruneArcs); } for (var key in objects) { pruneGeometry(objects[key]); } if (verbose) console.warn("prune: retained " + newArcCount + " / " + oldArcCount + " arcs (" + Math.round(newArcCount / oldArcCount * 100) + "%)"); return topology; }; function noop() { } }, {}], 14: [function (require, module, exports) { module.exports = function (objects, bbox, Q) { var x0 = isFinite(bbox[0]) ? bbox[0] : 0, y0 = isFinite(bbox[1]) ? bbox[1] : 0, x1 = isFinite(bbox[2]) ? bbox[2] : 0, y1 = isFinite(bbox[3]) ? bbox[3] : 0, kx = x1 - x0 ? (Q - 1) / (x1 - x0) : 1, ky = y1 - y0 ? (Q - 1) / (y1 - y0) : 1; function quantizeGeometry(geometry) { if (geometry && quantizeGeometryType.hasOwnProperty(geometry.type)) quantizeGeometryType[geometry.type](geometry); } var quantizeGeometryType = { GeometryCollection: function (o) { o.geometries.forEach(quantizeGeometry); }, Point: function (o) { quantizePoint(o.coordinates); }, MultiPoint: function (o) { o.coordinates.forEach(quantizePoint); }, LineString: function (o) { var line = o.coordinates; quantizeLine(line); if (line.length < 2) line[1] = line[0]; // must have 2+ }, MultiLineString: function (o) { for (var lines = o.coordinates, i = 0, n = lines.length; i < n; ++i) { var line = lines[i]; quantizeLine(line); if (line.length < 2) line[1] = line[0]; // must have 2+ } }, Polygon: function (o) { for (var rings = o.coordinates, i = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; quantizeLine(ring); while (ring.length < 4) ring.push(ring[0]); // must have 4+ } }, MultiPolygon: function (o) { for (var polygons = o.coordinates, i = 0, n = polygons.length; i < n; ++i) { for (var rings = polygons[i], j = 0, m = rings.length; j < m; ++j) { var ring = rings[j]; quantizeLine(ring); while (ring.length < 4) ring.push(ring[0]); // must have 4+ } } } }; function quantizePoint(coordinates) { coordinates[0] = Math.round((coordinates[0] - x0) * kx); coordinates[1] = Math.round((coordinates[1] - y0) * ky); } function quantizeLine(coordinates) { var i = 0, j = 1, n = coordinates.length, pi = coordinates[0], pj, px = pi[0] = Math.round((pi[0] - x0) * kx), py = pi[1] = Math.round((pi[1] - y0) * ky), x, y; while (++i < n) { pi = coordinates[i]; x = Math.round((pi[0] - x0) * kx); y = Math.round((pi[1] - y0) * ky); if (x !== px || y !== py) { // skip coincident points pj = coordinates[j++]; pj[0] = px = x; pj[1] = py = y; } } coordinates.length = j; } for (var key in objects) { quantizeGeometry(objects[key]); } return { scale: [1 / kx, 1 / ky], translate: [x0, y0] }; }; }, {}], 15: [function (require, module, exports) { var topojson = require("../../"), systems = require("./coordinate-systems"); module.exports = function (topology, options) { var minimumArea = 0, retainProportion, verbose = false, system = null, N = topology.arcs.reduce(function (p, v) { return p + v.length; }, 0), M = 0; if (options) "minimum-area" in options && (minimumArea = +options["minimum-area"]), "coordinate-system" in options && (system = systems[options["coordinate-system"]]), "retain-proportion" in options && (retainProportion = +options["retain-proportion"]), "verbose" in options && (verbose = !!options["verbose"]); topojson.presimplify(topology, system.triangleArea); if (retainProportion) { var areas = []; topology.arcs.forEach(function (arc) { arc.forEach(function (point) { areas.push(point[2]); }); }); options["minimum-area"] = minimumArea = N ? areas.sort(function (a, b) { return b - a; })[Math.ceil((N - 1) * retainProportion)] : 0; if (verbose) console.warn("simplification: effective minimum area " + minimumArea.toPrecision(3)); } topology.arcs.forEach(topology.transform ? function (arc) { var dx = 0, dy = 0, // accumulate removed points i = -1, j = -1, n = arc.length, source, target; while (++i < n) { source = arc[i]; if (source[2] >= minimumArea) { target = arc[++j]; target[0] = source[0] + dx; target[1] = source[1] + dy; dx = dy = 0; } else { dx += source[0]; dy += source[1]; } } arc.length = ++j; } : function (arc) { var i = -1, j = -1, n = arc.length, point; while (++i < n) { point = arc[i]; if (point[2] >= minimumArea) { arc[++j] = point; } } arc.length = ++j; }); // Remove computed area (z) for each point. // This is done as a separate pass because some coordinates may be shared // between arcs (such as the last point and first point of a cut line). topology.arcs.forEach(function (arc) { var i = -1, n = arc.length; while (++i < n) arc[i].length = 2; M += arc.length; }); if (verbose) console.warn("simplification: retained " + M + " / " + N + " points (" + Math.round((M / N) * 100) + "%)"); return topology; }; }, { "../../": 2, "./coordinate-systems": 8}], 16: [function (require, module, exports) { var π = Math.PI, π_4 = π / 4, radians = π / 180; exports.name = "spherical"; exports.formatDistance = formatDistance; exports.ringArea = ringArea; exports.absoluteArea = absoluteArea; exports.triangleArea = triangleArea; exports.distance = haversinDistance; // XXX why two implementations? function formatDistance(radians) { var km = radians * 6371; return (km > 1 ? km.toFixed(3) + "km" : (km * 1000).toPrecision(3) + "m") + " (" + (radians * 180 / Math.PI).toPrecision(3) + "°)"; } function ringArea(ring) { if (!ring.length) return 0; var area = 0, p = ring[0], λ = p[0] * radians, φ = p[1] * radians / 2 + π_4, λ0 = λ, cosφ0 = Math.cos(φ), sinφ0 = Math.sin(φ); for (var i = 1, n = ring.length; i < n; ++i) { p = ring[i], λ = p[0] * radians, φ = p[1] * radians / 2 + π_4; // Spherical excess E for a spherical triangle with vertices: south pole, // previous point, current point. Uses a formula derived from Cagnoli’s // theorem. See Todhunter, Spherical Trig. (1871), Sec. 103, Eq. (2). var dλ = λ - λ0, cosφ = Math.cos(φ), sinφ = Math.sin(φ), k = sinφ0 * sinφ, u = cosφ0 * cosφ + k * Math.cos(dλ), v = k * Math.sin(dλ); area += Math.atan2(v, u); // Advance the previous point. λ0 = λ, cosφ0 = cosφ, sinφ0 = sinφ; } return 2 * (area > π ? area - 2 * π : area < -π ? area + 2 * π : area); } function absoluteArea(a) { return a < 0 ? a + 4 * π : a; } function triangleArea(t) { var a = distance(t[0], t[1]), b = distance(t[1], t[2]), c = distance(t[2], t[0]), s = (a + b + c) / 2; return 4 * Math.atan(Math.sqrt(Math.max(0, Math.tan(s / 2) * Math.tan((s - a) / 2) * Math.tan((s - b) / 2) * Math.tan((s - c) / 2)))); } function distance(a, b) { var Δλ = (b[0] - a[0]) * radians, sinΔλ = Math.sin(Δλ), cosΔλ = Math.cos(Δλ), sinφ0 = Math.sin(a[1] * radians), cosφ0 = Math.cos(a[1] * radians), sinφ1 = Math.sin(b[1] * radians), cosφ1 = Math.cos(b[1] * radians), _; return Math.atan2(Math.sqrt((_ = cosφ1 * sinΔλ) * _ + (_ = cosφ0 * sinφ1 - sinφ0 * cosφ1 * cosΔλ) * _), sinφ0 * sinφ1 + cosφ0 * cosφ1 * cosΔλ); } function haversinDistance(x0, y0, x1, y1) { x0 *= radians, y0 *= radians, x1 *= radians, y1 *= radians; return 2 * Math.asin(Math.sqrt(haversin(y1 - y0) + Math.cos(y0) * Math.cos(y1) * haversin(x1 - x0))); } function haversin(x) { return (x = Math.sin(x / 2)) * x; } }, {}], 17: [function (require, module, exports) { var type = require("./type"); module.exports = function (objects, transform) { var ε = 1e-2, x0 = -180, x0e = x0 + ε, x1 = 180, x1e = x1 - ε, y0 = -90, y0e = y0 + ε, y1 = 90, y1e = y1 - ε, fragments = []; if (transform) { var kx = transform.scale[0], ky = transform.scale[1], dx = transform.translate[0], dy = transform.translate[1]; x0 = Math.round((x0 - dx) / kx); x1 = Math.round((x1 - dx) / kx); y0 = Math.round((y0 - dy) / ky); y1 = Math.round((y1 - dy) / ky); x0e = Math.round((x0e - dx) / kx); x1e = Math.round((x1e - dx) / kx); y0e = Math.round((y0e - dy) / ky); y1e = Math.round((y1e - dy) / ky); } function normalizePoint(y) { return y <= y0e ? [0, y0] // south pole : y >= y1e ? [0, y1] // north pole : [x0, y]; // antimeridian } var stitch = type({ polygon: function (polygon) { var rings = []; // For each ring, detect where it crosses the antimeridian or pole. for (var j = 0, m = polygon.length; j < m; ++j) { var ring = polygon[j], fragments = []; // By default, assume that this ring doesn’t need any stitching. fragments.push(ring); for (var i = 0, n = ring.length; i < n; ++i) { var point = ring[i], x = point[0], y = point[1]; // If this is an antimeridian or polar point… if (x <= x0e || x >= x1e || y <= y0e || y >= y1e) { // Advance through any antimeridian or polar points… for (var k = i + 1; k < n; ++k) { var pointk = ring[k], xk = pointk[0], yk = pointk[1]; if (xk > x0e && xk < x1e && yk > y0e && yk < y1e) break; } // If this was just a single antimeridian or polar point, // we don’t need to cut this ring into a fragment; // we can just leave it as-is. if (k === i + 1) continue; // Otherwise, if this is not the first point in the ring, // cut the current fragment so that it ends at the current point. // The current point is also normalized for later joining. if (i) { var fragmentBefore = ring.slice(0, i + 1); fragmentBefore[fragmentBefore.length - 1] = normalizePoint(y); fragments[fragments.length - 1] = fragmentBefore; } // If the ring started with an antimeridian fragment, // we can ignore that fragment entirely. else { fragments.pop(); } // If the remainder of the ring is an antimeridian fragment, // move on to the next ring. if (k >= n) break; // Otherwise, add the remaining ring fragment and continue. fragments.push(ring = ring.slice(k - 1)); ring[0] = normalizePoint(ring[0][1]); i = -1; n = ring.length; } } // Now stitch the fragments back together into rings. // To connect the fragments start-to-end, create a simple index by end. var fragmentByStart = {}, fragmentByEnd = {}; // For each fragment… for (var i = 0, n = fragments.length; i < n; ++i) { var fragment = fragments[i], start = fragment[0], end = fragment[fragment.length - 1]; // If this fragment is closed, add it as a standalone ring. if (start[0] === end[0] && start[1] === end[1]) { rings.push(fragment); fragments[i] = null; continue; } fragment.index = i; fragmentByStart[start] = fragmentByEnd[end] = fragment; } // For each open fragment… for (var i = 0; i < n; ++i) { var fragment = fragments[i]; if (fragment) { var start = fragment[0], end = fragment[fragment.length - 1], startFragment = fragmentByEnd[start], endFragment = fragmentByStart[end]; delete fragmentByStart[start]; delete fragmentByEnd[end]; // If this fragment is closed, add it as a standalone ring. if (start[0] === end[0] && start[1] === end[1]) { rings.push(fragment); continue; } if (startFragment) { delete fragmentByEnd[start]; delete fragmentByStart[startFragment[0]]; startFragment.pop(); // drop the shared coordinate fragments[startFragment.index] = null; fragment = startFragment.concat(fragment); if (startFragment === endFragment) { // Connect both ends to this single fragment to create a ring. rings.push(fragment); } else { fragment.index = n++; fragments.push(fragmentByStart[fragment[0]] = fragmentByEnd[fragment[fragment.length - 1]] = fragment); } } else if (endFragment) { delete fragmentByStart[end]; delete fragmentByEnd[endFragment[endFragment.length - 1]]; fragment.pop(); // drop the shared coordinate fragment = fragment.concat(endFragment); fragment.index = n++; fragments[endFragment.index] = null; fragments.push(fragmentByStart[fragment[0]] = fragmentByEnd[fragment[fragment.length - 1]] = fragment); } else { fragment.push(fragment[0]); // close ring rings.push(fragment); } } } } // Copy the rings into the target polygon. for (var i = 0, n = polygon.length = rings.length; i < n; ++i) { polygon[i] = rings[i]; } } }); for (var key in objects) { stitch.object(objects[key]); } }; }, { "./type": 28}], 18: [function (require, module, exports) { var type = require("./type"), stitch = require("./stitch"), systems = require("./coordinate-systems"), topologize = require("./topology/index"), delta = require("./delta"), geomify = require("./geomify"), prefilter = require("./prefilter"), quantize = require("./quantize"), bounds = require("./bounds"), computeId = require("./compute-id"), transformProperties = require("./transform-properties"); var ε = 1e-6; module.exports = function (objects, options) { var Q = 1e4, // precision of quantization id = function (d) { return d.id; }, // function to compute object id propertyTransform = function () { }, // function to transform properties transform, minimumArea = 0, stitchPoles = true, verbose = false, system = null; if (options) "verbose" in options && (verbose = !!options["verbose"]), "stitch-poles" in options && (stitchPoles = !!options["stitch-poles"]), "coordinate-system" in options && (system = systems[options["coordinate-system"]]), "minimum-area" in options && (minimumArea = +options["minimum-area"]), "quantization" in options && (Q = +options["quantization"]), "id" in options && (id = options["id"]), "property-transform" in options && (propertyTransform = options["property-transform"]); // Compute the new feature id and transform properties. computeId(objects, id); transformProperties(objects, propertyTransform); // Convert to geometry objects. geomify(objects); // Compute initial bounding box. var bbox = bounds(objects); // For automatic coordinate system determination, consider the bounding box. var oversize = bbox[0] < -180 - ε || bbox[1] < -90 - ε || bbox[2] > 180 + ε || bbox[3] > 90 + ε; if (!system) { system = systems[oversize ? "cartesian" : "spherical"]; if (options) options["coordinate-system"] = system.name; } if (system === systems.spherical) { if (oversize) throw new Error("spherical coordinates outside of [±180°, ±90°]"); // When near the spherical coordinate limits, clamp to nice round values. // This avoids quantized coordinates that are slightly outside the limits. if (bbox[0] < -180 + ε) bbox[0] = -180; if (bbox[1] < -90 + ε) bbox[1] = -90; if (bbox[2] > 180 - ε) bbox[2] = 180; if (bbox[3] > 90 - ε) bbox[3] = 90; } if (verbose) { console.warn("bounds: " + bbox.join(" ") + " (" + system.name + ")"); } // Filter rings smaller than the minimum area. // This can produce a simpler topology. if (minimumArea) prefilter(objects, function (ring) { return system.absoluteArea(system.ringArea(ring)) >= minimumArea; }); // Compute the quantization transform. if (Q) { transform = quantize(objects, bbox, Q); if (verbose) { console.warn("quantization: " + transform.scale.map(function (degrees) { return system.formatDistance(degrees / 180 * Math.PI); }).join(" ")); } } // Remove any antimeridian cuts and restitch. if (system === systems.spherical && stitchPoles) { stitch(objects, transform); } // Compute the topology. var topology = topologize(objects); topology.bbox = bbox; if (verbose) { console.warn("topology: " + topology.arcs.length + " arcs, " + topology.arcs.reduce(function (p, v) { return p + v.length; }, 0) + " points"); } // Convert to delta-encoding. if (Q) topology.transform = transform, delta(topology); return topology; }; }, { "./bounds": 4, "./compute-id": 7, "./coordinate-systems": 8, "./delta": 9, "./geomify": 11, "./prefilter": 12, "./quantize": 14, "./stitch": 17, "./topology/index": 23, "./transform-properties": 27, "./type": 28}], 19: [function (require, module, exports) { var join = require("./join"); // Given an extracted (pre-)topology, cuts (or rotates) arcs so that all shared // point sequences are identified. The topology can then be subsequently deduped // to remove exact duplicate arcs. module.exports = function (topology) { var junctionByPoint = join(topology), coordinates = topology.coordinates, lines = topology.lines, rings = topology.rings; for (var i = 0, n = lines.length; i < n; ++i) { var line = lines[i], lineMid = line[0], lineEnd = line[1]; while (++lineMid < lineEnd) { if (junctionByPoint.get(coordinates[lineMid])) { var next = { 0: lineMid, 1: line[1] }; line[1] = lineMid; line = line.next = next; } } } for (var i = 0, n = rings.length; i < n; ++i) { var ring = rings[i], ringStart = ring[0], ringMid = ringStart, ringEnd = ring[1], ringFixed = junctionByPoint.get(coordinates[ringStart]); while (++ringMid < ringEnd) { if (junctionByPoint.get(coordinates[ringMid])) { if (ringFixed) { var next = { 0: ringMid, 1: ring[1] }; ring[1] = ringMid; ring = ring.next = next; } else { // For the first junction, we can rotate rather than cut. rotateArray(coordinates, ringStart, ringEnd, ringEnd - ringMid); coordinates[ringEnd] = coordinates[ringStart]; ringFixed = true; ringMid = ringStart; // restart; we may have skipped junctions } } } } return topology; }; function rotateArray(array, start, end, offset) { reverse(array, start, end); reverse(array, start, start + offset); reverse(array, start + offset, end); } function reverse(array, start, end) { for (var mid = start + ((end-- - start) >> 1), t; start < mid; ++start, --end) { t = array[start], array[start] = array[end], array[end] = t; } } }, { "./join": 24}], 20: [function (require, module, exports) { var join = require("./join"), hashtable = require("./hashtable"), hashPoint = require("./point-hash"), equalPoint = require("./point-equal"); // Given a cut topology, combines duplicate arcs. module.exports = function (topology) { var coordinates = topology.coordinates, lines = topology.lines, rings = topology.rings, arcCount = lines.length + rings.length; delete topology.lines; delete topology.rings; // Count the number of (non-unique) arcs to initialize the hashtable safely. for (var i = 0, n = lines.length; i < n; ++i) { var line = lines[i]; while (line = line.next) ++arcCount; } for (var i = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; while (ring = ring.next) ++arcCount; } var arcsByEnd = hashtable(arcCount * 2, hashPoint, equalPoint), arcs = topology.arcs = []; for (var i = 0, n = lines.length; i < n; ++i) { var line = lines[i]; do { dedupLine(line); } while (line = line.next); } for (var i = 0, n = rings.length; i < n; ++i) { var ring = rings[i]; if (ring.next) { // arc is no longer closed do { dedupLine(ring); } while (ring = ring.next); } else { dedupRing(ring); } } function dedupLine(arc) { var startPoint, endPoint, startArcs, endArcs; // Does this arc match an existing arc in order? if (startArcs = arcsByEnd.get(startPoint = coordinates[arc[0]])) { for (var i = 0, n = startArcs.length; i < n; ++i) { var startArc = startArcs[i]; if (equalLine(startArc, arc)) { arc[0] = startArc[0]; arc[1] = startArc[1]; return; } } } // Does this arc match an existing arc in reverse order? if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[1]])) { for (var i = 0, n = endArcs.length; i < n; ++i) { var endArc = endArcs[i]; if (reverseEqualLine(endArc, arc)) { arc[1] = endArc[0]; arc[0] = endArc[1]; return; } } } if (startArcs) startArcs.push(arc); else arcsByEnd.set(startPoint, [arc]); if (endArcs) endArcs.push(arc); else arcsByEnd.set(endPoint, [arc]); arcs.push(arc); } function dedupRing(arc) { var endPoint, endArcs; // Does this arc match an existing line in order, or reverse order? // Rings are closed, so their start point and end point is the same. if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[0]])) { for (var i = 0, n = endArcs.length; i < n; ++i) { var endArc = endArcs[i]; if (equalRing(endArc, arc)) { arc[0] = endArc[0]; arc[1] = endArc[1]; return; } if (reverseEqualRing(endArc, arc)) { arc[0] = endArc[1]; arc[1] = endArc[0]; return; } } } // Otherwise, does this arc match an existing ring in order, or reverse order? if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[0] + findMinimumOffset(arc)])) { for (var i = 0, n = endArcs.length; i < n; ++i) { var endArc = endArcs[i]; if (equalRing(endArc, arc)) { arc[0] = endArc[0]; arc[1] = endArc[1]; return; } if (reverseEqualRing(endArc, arc)) { arc[0] = endArc[1]; arc[1] = endArc[0]; return; } } } if (endArcs) endArcs.push(arc); else arcsByEnd.set(endPoint, [arc]); arcs.push(arc); } function equalLine(arcA, arcB) { var ia = arcA[0], ib = arcB[0], ja = arcA[1], jb = arcB[1]; if (ia - ja !== ib - jb) return false; for (; ia <= ja; ++ia, ++ib) if (!equalPoint(coordinates[ia], coordinates[ib])) return false; return true; } function reverseEqualLine(arcA, arcB) { var ia = arcA[0], ib = arcB[0], ja = arcA[1], jb = arcB[1]; if (ia - ja !== ib - jb) return false; for (; ia <= ja; ++ia, --jb) if (!equalPoint(coordinates[ia], coordinates[jb])) return false; return true; } function equalRing(arcA, arcB) { var ia = arcA[0], ib = arcB[0], ja = arcA[1], jb = arcB[1], n = ja - ia; if (n !== jb - ib) return false; var ka = findMinimumOffset(arcA), kb = findMinimumOffset(arcB); for (var i = 0; i < n; ++i) { if (!equalPoint(coordinates[ia + (i + ka) % n], coordinates[ib + (i + kb) % n])) return false; } return true; } function reverseEqualRing(arcA, arcB) { var ia = arcA[0], ib = arcB[0], ja = arcA[1], jb = arcB[1], n = ja - ia; if (n !== jb - ib) return false; var ka = findMinimumOffset(arcA), kb = n - findMinimumOffset(arcB); for (var i = 0; i < n; ++i) { if (!equalPoint(coordinates[ia + (i + ka) % n], coordinates[jb - (i + kb) % n])) return false; } return true; } // Rings are rotated to a consistent, but arbitrary, start point. // This is necessary to detect when a ring and a rotated copy are dupes. function findMinimumOffset(arc) { var start = arc[0], end = arc[1], mid = start, minimum = mid, minimumPoint = coordinates[mid]; while (++mid < end) { var point = coordinates[mid]; if (point[0] < minimumPoint[0] || point[0] === minimumPoint[0] && point[1] < minimumPoint[1]) { minimum = mid; minimumPoint = point; } } return minimum - start; } return topology; }; }, { "./hashtable": 22, "./join": 24, "./point-equal": 25, "./point-hash": 26}], 21: [function (require, module, exports) { // Extracts the lines and rings from the specified hash of geometry objects. // // Returns an object with three properties: // // * coordinates - shared buffer of [x, y] coordinates // * lines - lines extracted from the hash, of the form [start, end] // * rings - rings extracted from the hash, of the form [start, end] // // For each ring or line, start and end represent inclusive indexes into the // coordinates buffer. For rings (and closed lines), coordinates[start] equals // coordinates[end]. // // For each line or polygon geometry in the input hash, including nested // geometries as in geometry collections, the `coordinates` array is replaced // with an equivalent `arcs` array that, for each line (for line string // geometries) or ring (for polygon geometries), points to one of the above // lines or rings. module.exports = function (objects) { var index = -1, lines = [], rings = [], coordinates = []; function extractGeometry(geometry) { if (geometry && extractGeometryType.hasOwnProperty(geometry.type)) extractGeometryType[geometry.type](geometry); } var extractGeometryType = { GeometryCollection: function (o) { o.geometries.forEach(extractGeometry); }, LineString: function (o) { o.arcs = extractLine(o.coordinates); delete o.coordinates; }, MultiLineString: function (o) { o.arcs = o.coordinates.map(extractLine); delete o.coordinates; }, Polygon: function (o) { o.arcs = o.coordinates.map(extractRing); delete o.coordinates; }, MultiPolygon: function (o) { o.arcs = o.coordinates.map(extractMultiRing); delete o.coordinates; } }; function extractLine(line) { for (var i = 0, n = line.length; i < n; ++i) coordinates[++index] = line[i]; var arc = { 0: index - n + 1, 1: index }; lines.push(arc); return arc; } function extractRing(ring) { for (var i = 0, n = ring.length; i < n; ++i) coordinates[++index] = ring[i]; var arc = { 0: index - n + 1, 1: index }; rings.push(arc); return arc; } function extractMultiRing(rings) { return rings.map(extractRing); } for (var key in objects) { extractGeometry(objects[key]); } return { type: "Topology", coordinates: coordinates, lines: lines, rings: rings, objects: objects }; }; }, {}], 22: [function (require, module, exports) { module.exports = function (size, hash, equal) { var hashtable = new Array(size = 1 << Math.ceil(Math.log(size) / Math.LN2)), mask = size - 1, free = size; function set(key, value) { var index = hash(key) & mask, match = hashtable[index], cycle = !index; while (match != null) { if (equal(match.key, key)) return match.value = value; match = hashtable[index = (index + 1) & mask]; if (!index && cycle++) throw new Error("full hashtable"); } hashtable[index] = { key: key, value: value }; --free; return value; } function get(key, missingValue) { var index = hash(key) & mask, match = hashtable[index], cycle = !index; while (match != null) { if (equal(match.key, key)) return match.value; match = hashtable[index = (index + 1) & mask]; if (!index && cycle++) break; } return missingValue; } function remove(key) { var index = hash(key) & mask, match = hashtable[index], cycle = !index; while (match != null) { if (equal(match.key, key)) { hashtable[index] = null; match = hashtable[index = (index + 1) & mask]; if (match != null) { // delete and re-add ++free; hashtable[index] = null; set(match.key, match.value); } ++free; return true; } match = hashtable[index = (index + 1) & mask]; if (!index && cycle++) break; } return false; } function keys() { var keys = []; for (var i = 0, n = hashtable.length; i < n; ++i) { var match = hashtable[i]; if (match != null) keys.push(match.key); } return keys; } return { set: set, get: get, remove: remove, keys: keys }; }; }, {}], 23: [function (require, module, exports) { var hashtable = require("./hashtable"), extract = require("./extract"), cut = require("./cut"), dedup = require("./dedup"); // Constructs the TopoJSON Topology for the specified hash of geometries. // Each object in the specified hash must be a GeoJSON object, // meaning FeatureCollection, a Feature or a geometry object. module.exports = function (objects) { var topology = dedup(cut(extract(objects))), coordinates = topology.coordinates, indexByArc = hashtable(topology.arcs.length, hashArc, equalArc); objects = topology.objects; // for garbage collection topology.arcs = topology.arcs.map(function (arc, i) { indexByArc.set(arc, i); return coordinates.slice(arc[0], arc[1] + 1); }); delete topology.coordinates; coordinates = null; function indexGeometry(geometry) { if (geometry && indexGeometryType.hasOwnProperty(geometry.type)) indexGeometryType[geometry.type](geometry); } var indexGeometryType = { GeometryCollection: function (o) { o.geometries.forEach(indexGeometry); }, LineString: function (o) { o.arcs = indexArcs(o.arcs); }, MultiLineString: function (o) { o.arcs = o.arcs.map(indexArcs); }, Polygon: function (o) { o.arcs = o.arcs.map(indexArcs); }, MultiPolygon: function (o) { o.arcs = o.arcs.map(indexMultiArcs); } }; function indexArcs(arc) { var indexes = []; do { var index = indexByArc.get(arc); indexes.push(arc[0] < arc[1] ? index : ~index); } while (arc = arc.next); return indexes; } function indexMultiArcs(arcs) { return arcs.map(indexArcs); } for (var key in objects) { indexGeometry(objects[key]); } return topology; }; function hashArc(arc) { var i = arc[0], j = arc[1], t; if (j < i) t = i, i = j, j = t; return i + 31 * j; } function equalArc(arcA, arcB) { var ia = arcA[0], ja = arcA[1], ib = arcB[0], jb = arcB[1], t; if (ja < ia) t = ia, ia = ja, ja = t; if (jb < ib) t = ib, ib = jb, jb = t; return ia === ib && ja === jb; } }, { "./cut": 19, "./dedup": 20, "./extract": 21, "./hashtable": 22}], 24: [function (require, module, exports) { var hashtable = require("./hashtable"), hashPoint = require("./point-hash"), equalPoint = require("./point-equal"); // Given an extracted (pre-)topology, identifies all of the junctions. These are // the points at which arcs (lines or rings) will need to be cut so that each // arc is represented uniquely. // // A junction is a point where at least one arc deviates from another arc going // through the same point. For example, consider the point B. If there is a arc // through ABC and another arc through CBA, then B is not a junction because in // both cases the adjacent point pairs are {A,C}. However, if there is an // additional arc ABD, then {A,D} != {A,C}, and thus B becomes a junction. // // For a closed ring ABCA, the first point A’s adjacent points are the second // and last point {B,C}. For a line, the first and last point are always // considered junctions, even if the line is closed; this ensures that a closed // line is never rotated. module.exports = function (topology) { var coordinates = topology.coordinates, lines = topology.lines, rings = topology.rings, visitedByPoint, neighborsByPoint = hashtable(coordinates.length, hashPoint, equalPoint), junctionByPoint = hashtable(coordinates.length, hashPoint, equalPoint); for (var i = 0, n = lines.length; i < n; ++i) { var line = lines[i], lineStart = line[0], lineEnd = line[1], previousPoint = null, currentPoint = coordinates[lineStart], nextPoint = coordinates[++lineStart]; visitedByPoint = hashtable(lineEnd - lineStart, hashPoint, equalPoint); junctionByPoint.set(currentPoint, true); // start while (++lineStart <= lineEnd) { sequence(previousPoint = currentPoint, currentPoint = nextPoint, nextPoint = coordinates[lineStart]); } junctionByPoint.set(nextPoint, true); // end } for (var i = 0, n = rings.length; i < n; ++i) { var ring = rings[i], ringStart = ring[0] + 1, ringEnd = ring[1], previousPoint = coordinates[ringEnd - 1], currentPoint = coordinates[ringStart - 1], nextPoint = coordinates[ringStart]; visitedByPoint = hashtable(ringEnd - ringStart + 1, hashPoint, equalPoint); sequence(previousPoint, currentPoint, nextPoint); while (++ringStart <= ringEnd) { sequence(previousPoint = currentPoint, currentPoint = nextPoint, nextPoint = coordinates[ringStart]); } } function sequence(previousPoint, currentPoint, nextPoint) { if (visitedByPoint.get(currentPoint)) return; // ignore self-intersection visitedByPoint.set(currentPoint, true); var neighbors = neighborsByPoint.get(currentPoint); if (neighbors) { if (!(equalPoint(neighbors[0], previousPoint) && equalPoint(neighbors[1], nextPoint)) && !(equalPoint(neighbors[0], nextPoint) && equalPoint(neighbors[1], previousPoint))) { junctionByPoint.set(currentPoint, true); } } else { neighborsByPoint.set(currentPoint, [previousPoint, nextPoint]); } } return junctionByPoint; }; }, { "./hashtable": 22, "./point-equal": 25, "./point-hash": 26}], 25: [function (require, module, exports) { module.exports = function (pointA, pointB) { return pointA[0] === pointB[0] && pointA[1] === pointB[1]; }; }, {}], 26: [function (require, module, exports) { // TODO if quantized, use simpler Int32 hashing? var hashBuffer = new ArrayBuffer(8), hashFloats = new Float64Array(hashBuffer), hashInts = new Int32Array(hashBuffer); function hashFloat(x) { hashFloats[0] = x; x = hashInts[1] ^ hashInts[0]; x ^= (x >>> 20) ^ (x >>> 12); x ^= (x >>> 7) ^ (x >>> 4); return x; } module.exports = function (point) { var h = (hashFloat(point[0]) + 31 * hashFloat(point[1])) | 0; return h < 0 ? ~h : h; }; }, {}], 27: [function (require, module, exports) { // Given a hash of GeoJSON objects, transforms any properties on features using // the specified transform function. The function is invoked for each existing // property on the current feature, being passed the new properties hash, the // property name, and the property value. The function is then expected to // assign a new value to the given property hash if the feature is to be // retained and return true. Or, to skip the property, do nothing and return // false. If no properties are propagated to the new properties hash, the // properties hash will be deleted from the current feature. module.exports = function (objects, propertyTransform) { if (arguments.length < 2) propertyTransform = function () { }; function transformObject(object) { if (object && transformObjectType.hasOwnProperty(object.type)) transformObjectType[object.type](object); } function transformFeature(feature) { if (feature.properties) { var properties0 = feature.properties, properties1 = {}, empty = true; for (var key0 in properties0) { if (propertyTransform(properties1, key0, properties0[key0])) { empty = false; } } if (empty) delete feature.properties; else feature.properties = properties1; } } var transformObjectType = { Feature: transformFeature, FeatureCollection: function (collection) { collection.features.forEach(transformFeature); } }; for (var key in objects) { transformObject(objects[key]); } return objects; }; }, {}], 28: [function (require, module, exports) { module.exports = function (types) { for (var type in typeDefaults) { if (!(type in types)) { types[type] = typeDefaults[type]; } } types.defaults = typeDefaults; return types; }; var typeDefaults = { Feature: function (feature) { if (feature.geometry) this.geometry(feature.geometry); }, FeatureCollection: function (collection) { var features = collection.features, i = -1, n = features.length; while (++i < n) this.Feature(features[i]); }, GeometryCollection: function (collection) { var geometries = collection.geometries, i = -1, n = geometries.length; while (++i < n) this.geometry(geometries[i]); }, LineString: function (lineString) { this.line(lineString.coordinates); }, MultiLineString: function (multiLineString) { var coordinates = multiLineString.coordinates, i = -1, n = coordinates.length; while (++i < n) this.line(coordinates[i]); }, MultiPoint: function (multiPoint) { var coordinates = multiPoint.coordinates, i = -1, n = coordinates.length; while (++i < n) this.point(coordinates[i]); }, MultiPolygon: function (multiPolygon) { var coordinates = multiPolygon.coordinates, i = -1, n = coordinates.length; while (++i < n) this.polygon(coordinates[i]); }, Point: function (point) { this.point(point.coordinates); }, Polygon: function (polygon) { this.polygon(polygon.coordinates); }, object: function (object) { return object == null ? null : typeObjects.hasOwnProperty(object.type) ? this[object.type](object) : this.geometry(object); }, geometry: function (geometry) { return geometry == null ? null : typeGeometries.hasOwnProperty(geometry.type) ? this[geometry.type](geometry) : null; }, point: function () { }, line: function (coordinates) { var i = -1, n = coordinates.length; while (++i < n) this.point(coordinates[i]); }, polygon: function (coordinates) { var i = -1, n = coordinates.length; while (++i < n) this.line(coordinates[i]); } }; var typeGeometries = { LineString: 1, MultiLineString: 1, MultiPoint: 1, MultiPolygon: 1, Point: 1, Polygon: 1, GeometryCollection: 1 }; var typeObjects = { Feature: 1, FeatureCollection: 1 }; }, {}], 29: [function (require, module, exports) { !function () { var topojson = { version: "1.4.6", mesh: mesh, feature: featureOrCollection, neighbors: neighbors, presimplify: presimplify }; function merge(topology, arcs) { var fragmentByStart = {}, fragmentByEnd = {}; arcs.forEach(function (i) { var e = ends(i), start = e[0], end = e[1], f, g; if (f = fragmentByEnd[start]) { delete fragmentByEnd[f.end]; f.push(i); f.end = end; if (g = fragmentByStart[end]) { delete fragmentByStart[g.start]; var fg = g === f ? f : f.concat(g); fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg; } else if (g = fragmentByEnd[end]) { delete fragmentByStart[g.start]; delete fragmentByEnd[g.end]; var fg = f.concat(g.map(function (i) { return ~i; }).reverse()); fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.start] = fg; } else { fragmentByStart[f.start] = fragmentByEnd[f.end] = f; } } else if (f = fragmentByStart[end]) { delete fragmentByStart[f.start]; f.unshift(i); f.start = start; if (g = fragmentByEnd[start]) { delete fragmentByEnd[g.end]; var gf = g === f ? f : g.concat(f); fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf; } else if (g = fragmentByStart[start]) { delete fragmentByStart[g.start]; delete fragmentByEnd[g.end]; var gf = g.map(function (i) { return ~i; }).reverse().concat(f); fragmentByStart[gf.start = g.end] = fragmentByEnd[gf.end = f.end] = gf; } else { fragmentByStart[f.start] = fragmentByEnd[f.end] = f; } } else if (f = fragmentByStart[start]) { delete fragmentByStart[f.start]; f.unshift(~i); f.start = end; if (g = fragmentByEnd[end]) { delete fragmentByEnd[g.end]; var gf = g === f ? f : g.concat(f); fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf; } else if (g = fragmentByStart[end]) { delete fragmentByStart[g.start]; delete fragmentByEnd[g.end]; var gf = g.map(function (i) { return ~i; }).reverse().concat(f); fragmentByStart[gf.start = g.end] = fragmentByEnd[gf.end = f.end] = gf; } else { fragmentByStart[f.start] = fragmentByEnd[f.end] = f; } } else if (f = fragmentByEnd[end]) { delete fragmentByEnd[f.end]; f.push(~i); f.end = start; if (g = fragmentByEnd[start]) { delete fragmentByStart[g.start]; var fg = g === f ? f : f.concat(g); fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg; } else if (g = fragmentByStart[start]) { delete fragmentByStart[g.start]; delete fragmentByEnd[g.end]; var fg = f.concat(g.map(function (i) { return ~i; }).reverse()); fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.start] = fg; } else { fragmentByStart[f.start] = fragmentByEnd[f.end] = f; } } else { f = [i]; fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f; } }); function ends(i) { var arc = topology.arcs[i], p0 = arc[0], p1 = [0, 0]; arc.forEach(function (dp) { p1[0] += dp[0], p1[1] += dp[1]; }); return [p0, p1]; } var fragments = []; for (var k in fragmentByEnd) fragments.push(fragmentByEnd[k]); return fragments; } function mesh(topology, o, filter) { var arcs = []; if (arguments.length > 1) { var geomsByArc = [], geom; function arc(i) { if (i < 0) i = ~i; (geomsByArc[i] || (geomsByArc[i] = [])).push(geom); } function line(arcs) { arcs.forEach(arc); } function polygon(arcs) { arcs.forEach(line); } function geometry(o) { if (o.type === "GeometryCollection") o.geometries.forEach(geometry); else if (o.type in geometryType) { geom = o; geometryType[o.type](o.arcs); } } var geometryType = { LineString: line, MultiLineString: polygon, Polygon: polygon, MultiPolygon: function (arcs) { arcs.forEach(polygon); } }; geometry(o); geomsByArc.forEach(arguments.length < 3 ? function (geoms, i) { arcs.push(i); } : function (geoms, i) { if (filter(geoms[0], geoms[geoms.length - 1])) arcs.push(i); }); } else { for (var i = 0, n = topology.arcs.length; i < n; ++i) arcs.push(i); } return object(topology, { type: "MultiLineString", arcs: merge(topology, arcs) }); } function featureOrCollection(topology, o) { return o.type === "GeometryCollection" ? { type: "FeatureCollection", features: o.geometries.map(function (o) { return feature(topology, o); }) } : feature(topology, o); } function feature(topology, o) { var f = { type: "Feature", id: o.id, properties: o.properties || {}, geometry: object(topology, o) }; if (o.id == null) delete f.id; return f; } function object(topology, o) { var absolute = transformAbsolute(topology.transform), arcs = topology.arcs; function arc(i, points) { if (points.length) points.pop(); for (var a = arcs[i < 0 ? ~i : i], k = 0, n = a.length, p; k < n; ++k) { points.push(p = a[k].slice()); absolute(p, k); } if (i < 0) reverse(points, n); } function point(p) { p = p.slice(); absolute(p, 0); return p; } function line(arcs) { var points = []; for (var i = 0, n = arcs.length; i < n; ++i) arc(arcs[i], points); if (points.length < 2) points.push(points[0].slice()); return points; } function ring(arcs) { var points = line(arcs); while (points.length < 4) points.push(points[0].slice()); return points; } function polygon(arcs) { return arcs.map(ring); } function geometry(o) { var t = o.type; return t === "GeometryCollection" ? { type: t, geometries: o.geometries.map(geometry) } : t in geometryType ? { type: t, coordinates: geometryType[t](o) } : null; } var geometryType = { Point: function (o) { return point(o.coordinates); }, MultiPoint: function (o) { return o.coordinates.map(point); }, LineString: function (o) { return line(o.arcs); }, MultiLineString: function (o) { return o.arcs.map(line); }, Polygon: function (o) { return polygon(o.arcs); }, MultiPolygon: function (o) { return o.arcs.map(polygon); } }; return geometry(o); } function reverse(array, n) { var t, j = array.length, i = j - n; while (i < --j) t = array[i], array[i++] = array[j], array[j] = t; } function bisect(a, x) { var lo = 0, hi = a.length; while (lo < hi) { var mid = lo + hi >>> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } function neighbors(objects) { var indexesByArc = {}, // arc index -> array of object indexes neighbors = objects.map(function () { return []; }); function line(arcs, i) { arcs.forEach(function (a) { if (a < 0) a = ~a; var o = indexesByArc[a]; if (o) o.push(i); else indexesByArc[a] = [i]; }); } function polygon(arcs, i) { arcs.forEach(function (arc) { line(arc, i); }); } function geometry(o, i) { if (o.type === "GeometryCollection") o.geometries.forEach(function (o) { geometry(o, i); }); else if (o.type in geometryType) geometryType[o.type](o.arcs, i); } var geometryType = { LineString: line, MultiLineString: polygon, Polygon: polygon, MultiPolygon: function (arcs, i) { arcs.forEach(function (arc) { polygon(arc, i); }); } }; objects.forEach(geometry); for (var i in indexesByArc) { for (var indexes = indexesByArc[i], m = indexes.length, j = 0; j < m; ++j) { for (var k = j + 1; k < m; ++k) { var ij = indexes[j], ik = indexes[k], n; if ((n = neighbors[ij])[i = bisect(n, ik)] !== ik) n.splice(i, 0, ik); if ((n = neighbors[ik])[i = bisect(n, ij)] !== ij) n.splice(i, 0, ij); } } } return neighbors; } function presimplify(topology, triangleArea) { var absolute = transformAbsolute(topology.transform), relative = transformRelative(topology.transform), heap = minHeap(compareArea), maxArea = 0, triangle; if (!triangleArea) triangleArea = cartesianArea; topology.arcs.forEach(function (arc) { var triangles = []; arc.forEach(absolute); for (var i = 1, n = arc.length - 1; i < n; ++i) { triangle = arc.slice(i - 1, i + 2); triangle[1][2] = triangleArea(triangle); triangles.push(triangle); heap.push(triangle); } // Always keep the arc endpoints! arc[0][2] = arc[n][2] = Infinity; for (var i = 0, n = triangles.length; i < n; ++i) { triangle = triangles[i]; triangle.previous = triangles[i - 1]; triangle.next = triangles[i + 1]; } }); while (triangle = heap.pop()) { var previous = triangle.previous, next = triangle.next; // If the area of the current point is less than that of the previous point // to be eliminated, use the latter's area instead. This ensures that the // current point cannot be eliminated without eliminating previously- // eliminated points. if (triangle[1][2] < maxArea) triangle[1][2] = maxArea; else maxArea = triangle[1][2]; if (previous) { previous.next = next; previous[2] = triangle[2]; update(previous); } if (next) { next.previous = previous; next[0] = triangle[0]; update(next); } } topology.arcs.forEach(function (arc) { arc.forEach(relative); }); function update(triangle) { heap.remove(triangle); triangle[1][2] = triangleArea(triangle); heap.push(triangle); } return topology; }; function cartesianArea(triangle) { return Math.abs( (triangle[0][0] - triangle[2][0]) * (triangle[1][1] - triangle[0][1]) - (triangle[0][0] - triangle[1][0]) * (triangle[2][1] - triangle[0][1]) ); } function compareArea(a, b) { return a[1][2] - b[1][2]; } function minHeap(compare) { var heap = {}, array = []; heap.push = function () { for (var i = 0, n = arguments.length; i < n; ++i) { var object = arguments[i]; up(object.index = array.push(object) - 1); } return array.length; }; heap.pop = function () { var removed = array[0], object = array.pop(); if (array.length) { array[object.index = 0] = object; down(0); } return removed; }; heap.remove = function (removed) { var i = removed.index, object = array.pop(); if (i !== array.length) { array[object.index = i] = object; (compare(object, removed) < 0 ? up : down)(i); } return i; }; function up(i) { var object = array[i]; while (i > 0) { var up = ((i + 1) >> 1) - 1, parent = array[up]; if (compare(object, parent) >= 0) break; array[parent.index = i] = parent; array[object.index = i = up] = object; } } function down(i) { var object = array[i]; while (true) { var right = (i + 1) << 1, left = right - 1, down = i, child = array[down]; if (left < array.length && compare(array[left], child) < 0) child = array[down = left]; if (right < array.length && compare(array[right], child) < 0) child = array[down = right]; if (down === i) break; array[child.index = i] = child; array[object.index = i = down] = object; } } return heap; } function transformAbsolute(transform) { if (!transform) return noop; var x0, y0, kx = transform.scale[0], ky = transform.scale[1], dx = transform.translate[0], dy = transform.translate[1]; return function (point, i) { if (!i) x0 = y0 = 0; point[0] = (x0 += point[0]) * kx + dx; point[1] = (y0 += point[1]) * ky + dy; }; } function transformRelative(transform) { if (!transform) return noop; var x0, y0, kx = transform.scale[0], ky = transform.scale[1], dx = transform.translate[0], dy = transform.translate[1]; return function (point, i) { if (!i) x0 = y0 = 0; var x1 = (point[0] - dx) / kx | 0, y1 = (point[1] - dy) / ky | 0; point[0] = x1 - x0; point[1] = y1 - y0; x0 = x1; y0 = y1; }; } function noop() { } if (typeof define === "function" && define.amd) define(topojson); if (typeof module === "object" && module.exports) { module.exports = topojson; this.topojson = topojson; } else this.topojson = topojson; } (); }, {}] }, {}, [2, 1]);